package com.demo.jzoffer2;

import com.demo.domain.TreeNode;
import org.junit.Test;

/**
 * @author gy
 * @date 2023/01/12
 */
public class Test0208_03 {
    /**
     * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
     *
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     *        5
     *       / \
     *      3   6
     *     / \
     *    2   4
     *   /
     *  1
     * 输出: 4
     *
     * 1 ≤ k ≤ 二叉搜索树元素个数
     * @param root
     * @param k
     * @return
     */

    int count,res; // 利用count记录迭代过程中形参k的变化，利用res记录返回的结果 使用 类变量
    public int kthLargest(TreeNode root, int k) {
        count = k;// 初始化count的值
        dfs(root);//这里不要引入形参k，dfs中直接使用的是初始值为k的类变量count
        return res;
    }

    /**
     * 进行深度优先遍历 二叉搜索树中序遍历（所有值单调递增） 倒叙是为了处理第k大的值
     * @param root
     */
    public void dfs(TreeNode root){
        if (root == null || count == 0){
            return; //当root为空或者已经找到了res时，直接返回 提升性能
        }
        dfs(root.right);
        if (--count == 0){//先-- 后判断 count值变为0 时 为目标
            res = root.val;
            return; // 此处return 避免之后的无效迭代dfs(root.left);
        }
        dfs(root.left);
    }


    @Test
    public void m1() {
    }

    @Test
    public void m2() {

    }

}
